// Package _5_ReplaceSpace
// Date        : 2022/12/5 16:05
// Version     : 1.0.0
// Author      : 代码小学生王木木
// Email       : 18574945291@163.com
// Description : https://leetcode.cn/problems/ti-huan-kong-ge-lcof/?favorite=xb9nqhhg
package main

// 从后往前替换，避免频繁移动
func replaceSpace(s string) string {
	if len(s) == 0 {
		return s
	}
	oldLen := len(s)
	spaceNum := 0

	for i := 0; i < oldLen; i++ {
		if s[i] == ' ' {
			spaceNum++
		}
	}
	// 特判，优化，如果没有空格，直接返回
	if spaceNum == 0 {
		return s
	}

	newLen := oldLen + 2*spaceNum
	arr := make([]byte, newLen)
	i, j := oldLen-1, newLen-1
	for i >= 0 && j >= 0 {
		if s[i] != ' ' {
			arr[j] = s[i]
			j--
			i--
			continue
		}
		arr[j] = '0'
		j--
		arr[j] = '2'
		j--
		arr[j] = '%'
		j--
		i--
	}

	return string(arr)
}

func main() {
	replaceSpace(" ")
}
